package org.nowcoder.leetcode.DP;

/**
 * Title  : 53. Maximum Subarray
 * Source : https://leetcode.cn/problems/maximum-subarray/description/
 * Author : XrazYang
 * Date   : 2023-12-14
 */
public class LeetCode_53 {
    public int maxSubArray(int[] nums) {
        //1. /定义状态： dp[i]表示以 nums[i] 结尾的连续子数组的最大和
        int[] dp = new int[nums.length];

        //1. 初始状态
        dp[0] = nums[0];
        int result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            //3. 状态转移方程
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            result = Math.max(result, dp[i]);
        }
        return result;
    }

}
